The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs require matching packets on a subset of fields of the packet flow label, with the semantics of a sequential search through the ACL rules. IP forwarding requires a longest prefix match.
Known approaches of packet classification include using custom application-specific integrated circuits (ASICs), custom circuitry, software or firmware controlled processors, and associative memories, including, but not limited to binary content-addressable memories (binary CAMs) and ternary content-addressable memories (ternary CAMs or TCAMs). Each entry of a binary CAM typically includes a value for matching against, while each TCAM entry typically includes a value and a mask. The associative memory compares a lookup word against all of the entries in parallel, and typically generates an indication of the highest priority entry that matches the lookup word. An entry matches the lookup word in a binary CAM if the lookup word and the entry value are identical, while an entry matches the lookup word in a TCAM if the lookup word and the entry value are identical in the bits that are not indicated by the mask as being irrelevant to the comparison operations.
Associative memories are very useful in performing packet classification operations. In performing a packet classification, it is not uncommon for multiple lookup operations to be performed in parallel or in series using multiple as sociative memories basically based on a same search key or variant thereof, as one lookup operation might be related to packet forwarding while another related to quality of service determination. These associative memories may be built by different vendors, albeit typically to the same specification. However, some vendors might use different technologies or implement associative memories which operate faster than the specification. If a system is built to handle the worst case or specification values, it might not operate as fast or as efficient as it could if it was tailored to the specific parameters of the implemented devices.
For example, some vendors might use DRAM or other memory technology which requires idle time (e.g., idle or dead cycles, time delay, etc.) to refresh its memory. A known system always provides a worst case maximum number of idle cycles at minimal timing intervals to ensure that each associative memory has enough time to refresh its memory. However, even though the associative memory does not require refreshing or can refresh faster than the specification requires, the system still provides these idle cycles. Thus, the system does not always operate as fast nor as efficiently as its devices would allow it to operate. Similarly, some instructions or lookup operations may be performed by different implementations of associative memories in different amounts of time. Desired are new functionality, features, and mechanisms in associative memories and other devices to adapt to the capabilities of the devices used to implement a system.